package com.learn.algorithm_783;

import com.dataconsruct.TreeNode;
import com.dataconsruct.TreeOperation;
import org.junit.Test;

/**
 * 二叉搜索树节点最小距离
 * https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
 * @author gatts, 2022/1/12 22:15
 */
public class NearestDistanceInTreeNode {

    @Test
    public void test() {
        TreeNode root = new TreeNode(90);
        root.left = new TreeNode(69, new TreeNode(49, null, new TreeNode(52)), new TreeNode(89));
        TreeOperation.show(root);
        System.out.println("--------------  分割线  ----------------");
        System.out.println("最小差值：" + minDiffInBST(root));
    }

    /**
     * 中序遍历二叉树（是按照从小到大顺序的），
     *      按遍历顺序的相邻节点之间的差值的最小值就是结果了
     */
    public int minDiffInBST(TreeNode root) {
        minVal(root);
        return subtract;
    }

    // 按遍历顺序，上一个节点的值
    Integer previous;
    // 差值
    int subtract = Integer.MAX_VALUE;

    private void minVal(TreeNode node) {
        if (node == null) {
            return;
        }
        minVal(node.left);

        System.out.println(node.val);
        if (previous != null) {
            // 升序遍历，后面的节点值一定更大
            subtract = Math.min(subtract, node.val - previous);
            // 最小也就是差值为 1了
            if (subtract == 1) {
                return;
            }
        }
        previous = node.val;

        minVal(node.right);
    }


    /**
     * 这是求所有根节点和左右子树之间最小差值（跟本题无关）
     * @param root
     */
//    @Deprecated
//    public int minDiffInBST(TreeNode root) {
//        if (root == null) {
//            return Integer.MAX_VALUE;
//        }
//        if (root.left == null && root.right != null) {
//            return Math.min(root.right.val - root.val, minDiffInBST(root.right));
//        }
//        if (root.left != null && root.right == null) {
//            return Math.min(root.val - root.left.val, minDiffInBST(root.left));
//        }
//        if (root.left == null && root.right == null) {
//            return Integer.MAX_VALUE;
//        }
//        int min = Math.min(root.val - root.left.val, root.right.val - root.val);
//        return Math.min(min, Math.min(minDiffInBST(root.left), minDiffInBST(root.right)));
//    }

}
